There are a variety of methods currently available for classifying and routing packets in communication systems. In particular, in Internet packet classification systems, rules tables are used to classify and route incoming packets. For each incoming packet, the best rule that matches the incoming data is selected, and the action corresponding to the matched rule is performed.
Typically, in one-dimensional packet classification, each rule is either a prefix or a range of data. The incoming data, usually the packet header data, is used to determine the destination address of the packet. The classification is performed in a dynamic router table having rule tables comprising an array of a fixed size collection of elements, or tuples. In a one-dimensional packet classification scheme, a tuple commonly comprises a rule or prefix, and a destination address. The classification scheme matches the appropriate header information to incoming data packets according to the rules. Once the information is matched to a rule, the router acts according to the matched rule by routing the data packet to the appropriate destination address, or next hop.
Substantial research has been done on one-dimensional classifiers in which each rule is a prefix. The length of a prefix is limited by the length W of the destination address (i.e., W=32 for IPv4 destination addresses and W=128 for IPv6 destination addresses). Where each rule is a prefix, the router table is referred to as a prefix router-table. In prefix router-tables, the best rule for matching a destination address is by matching the longest prefix to the destination address. Hence, prefix router-tables use what is commonly termed “longest-prefix matching” to classify (or lookup) packets.
TRIE data structures are used to build systems that can extract information in a computational complexity order of one. The TRIE data structure, whose nomenclature originates from the middle section of the word “retrieval,” is based on two principles: a fixed set of indices and hierarchical indexing. A fixed set of indices is derived when data is indexed by, for example, numerical digits or by the alphabet. Thus, each index is an array of elements (i.e., in the case where data is indexed by the numerical digits 0-9, a 10-element array is derived) wherein each of the array's element can point to another array. The hierarchical indexing depends on the amount of data stored in the TRIE data structure. Each element of data is stored at the highest level of the hierarchy based on retrieval uniqueness. As greater amounts of data are loaded onto the data structure, data elements with decreased retrieval uniqueness are “pushed down” or indexed at a lower level of the hierarchy.
Several TRIE-based data structures for prefix router-tables have been proposed that can perform each of the dynamic router-table operations (lookup, insert, delete) in O(W) time. Others structures attempt to optimize lookup time and memory requirement through an expensive preprocessing step. These structures, while providing very fast lookup capability, have a prohibitive insert/delete time. Therefore, these structures are suitable only for static router-tables (i.e., tables into/from which no inserts and deletes take place).
For example, a scheme has been proposed that performs a binary search on hash tables organized by prefix length (Waldvogel et al., “Scalable high speed IP routing lookups,” ACM SIGCOMM, 25-36 (1997)). This binary search scheme has an expected complexity of O(log W) for lookup. An alternative adaptation of binary search to longest-prefix matching was developed by Hari, et al., “Detecting and resolving packet filter conflicts,” IEEE INFOCOM (2000). Under this adaptation, a lookup in a table that has n prefixes takes O(W+log n) time. Because these schemes require expensive pre-computation, they are not suitable for dynamic router-tables.
In “Multiway range trees: Scalable IP lookup with fast updates,” GLOBECOM (2001), Suri et al., propose a B-tree data structure for dynamic router tables that provides finding of L M P(d) in O(log n) time. However, inserts/deletes take O(W log n) time. When W bits fit in O(1) words (as is the case for IPv4 and IPv6 prefixes) logical operations on W-bit vectors can be done in O(1) time each. In this case, the Suri et al. scheme takes O(W+log n) time for an update.
Additionally, a data structure has been developed called a collection of red-black trees (CRBT) that supports the three operations of a dynamic prefix-router table in O(log n) time each. It has been demonstrated that CRBT structure can easily be modified to extend the biased-skip-list structure of Ergun et al. (“A dynamic lookup scheme for bursty access patterns,” IEEE INFOCOM (2001)) to obtain a biased-skip-list structure for dynamic prefix-router-tables. Using this modified based-skip-list structure, lookup, insert, and delete can each be done in O(log n) time. Like the original biased-skip list structure of Ergun et al., the modified CRBT structure adapts so as to perform lookups faster for bursty access patterns than for non-bursty patterns. The CRBT structure may also be adapted to obtain a collection of splay trees structures, which performs the three dynamic prefix-router-table operations in O(log n) amortized time and which adapts to provide faster lookups for bursty traffic.
A model has been developed for table-driven route lookup that casts the table design problem as an optimization problem within the model (Cheung and McCanne, “Optimal routing table design for IP address lookups under memory constraints,” IEEE INFOCOM (1999)). The Cheung and McCanne model accounts for the memory hierarchy of modern computers and they optimize average performance rather than worst-case performance.
Hardware solutions that involve the use of content addressable memory as well as solutions that involve modifications to the Internet Protocol (i.e., the addition of information to each packet) have also been proposed.
In addition to prefix routing, range routing can also be used. In a range router-table, each rule is a range of destination addresses. Several criteria have been proposed to select the best rule that matches a given destination address—first matching-rule in table, highest-priority rule that matches the address, and so on. Two data structures have been developed for dynamic range-router-tables—heap on TRIE (HOT) and binary search tree on TRIE (BOT) (see Gupta and McKeown, “Dynamic algorithms with worst-case performance for packet classification,” IFIP Networking (2000). Both of these data structures are for cases when the best-matching rule is the highest-priority rule that matches the given destination address. The HOT takes O(W) time for a lookup and O(W log n) time for an insert or delete. The BOT structure takes O(W log n) time for a lookup and O(W) time for an insert/delete. However it would be desirable to reduce these times as much as possible to efficiently route packets.
In addition to the above mentioned papers, a number of U.S. Patents and published applications address dynamic routing schemes including, but not limited to U.S. Pat. Nos.: 6,341,130; 6,335,932; 6,289,013; 6,212,184; 6,157,955; 6,092,072; 6,061,712; 6,041,053; 6,021,131; 6,018,524; 5,909,440; 5,787,430; 5,701,467; 5,555,405; 4,833,468; 4,251,861; and published patent application Ser. No. 2002/0009076. Unfortunately, these references do not disclose schemes that adequately reduce the time in routing packets.
Accordingly, there is a need in the art for a dynamic data table routing structure to provide more effective ways to classify and route data packets. Specifically, a data table routing structure is needed to provide a quicker and more memory efficient method to search, insert, and delete items in a dynamic router data table.